1. Field of the Invention
The present invention relates to logical circuit design, and in particular the invention is directed to a failure-free synchronizer.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever.
2. Background Art
Most of today""s logical circuit design is synchronous. Synchronous logical circuit design follows an assumption that all components within a system follow a global (system-wide) clock cycle. Events and interactions among various parts can be assumed to happen at discrete time cycles marked by the global clock. Having this assumption can greatly simplify circuit design. As such most of the computers and electronic equipment available today are synchronous.
One area of focus within logical circuit design is building synchronizers. A synchronizer is a circuit that samples a data input. For example, a synchronizer can be used in a computer to detect whether a user has pressed a key on the keyboard. In this case, the data input is the signal that is transmitted from the keyboard to the computer processor when a key is pressed. The synchronizer polls the system bus (a place where the computer receives signals from different components) to see whether a signal from the keyboard has arrived. The polling (sampling) is done at periodic intervals. So in essence the synchronizer is constantly asking xe2x80x9chas a key been pressed on the keyboard at this clock cycle?xe2x80x9d Other example uses of synchronizers include sampling data that is transferred among parts of a computer (e.g. hard drives) or among different computers across a network.
Synchronization Failure
In the context of synchronous systems that engaged in high-speed communications between independent clock domains, circuit designers found a new class of problems related to using a synchronizer to accept an unsynchronized signal into a clock domain. One of the problems is called synchronization failure. For example, synchronization failure occurs sometimes when a computer system uses a synchronizer to accept signals from external sources that do not follow its own clock cycles. Sometimes the problem occurs within a computer system, where synchronizers are used to synchronize high-speed communication among components that have disparate clock systems.
To better understand synchronization failure, consider again the hypothetical keyboard example (though in real life the keyboard may not be sending high-speed signals that would cause failure). When a user presses a key, the circuit transmits a xe2x80x9c1xe2x80x9d signal to the synchronizer. At every clock cycle, the computer system also sends periodic control signals of xe2x80x9c1xe2x80x9d to the synchronizer to notify that it is time to sample. Thus the synchronizer has to watch for two input signals. If the keyboard signal arrives in the interval between two samplings and remains xe2x80x9c1xe2x80x9d until the synchronizer receives the next xe2x80x9c1xe2x80x9d from the clock and samples again, then the synchronizer should have no problem recognizing and acknowledging this keyboard signal. If, however, the keyboard signal is withdrawn because the user has let go of the key right before the next clock signal arrives, then there is potential for synchronization failure. In the circuit the withdrawal will be represented by the keyboard signal going from xe2x80x9c1xe2x80x9d back to xe2x80x9c0xe2x80x9d, which represents no signal. Failure can also occur in the situation when a xe2x80x9c0xe2x80x9d switches to a xe2x80x9c1xe2x80x9d. Research and practical experiences have shown that the synchronizer may not be able to determine if the switch happens before or after the arrival of the control signal from the system clock. The assumptions of classical physics shows that it is impossible for any device to determine, within a bounded time period, the correct ordering of these two eventsxe2x80x94the arrival of an unsynchronized switch in input signal and the arrival of a synchronized control signal. However, the device is guaranteed to decide eventually. The state in which the synchronizer is deciding is called the metastable state. If the metastable state lasts a very long time, a failure can occur in a synchronous system. As such, designers of synchronous systems have to accept certain risk of system failure. In many instances, they are able to reduce the occurrence of such risk to an infinitesimally small number by adding latency in circuits that can slow down overall system performance.
Asynchronous Arbiter
Prior art attempts in solving the synchronization failure include using asynchronous arbiters for the purpose of synchronization. An arbiter is a device that determines whether a particular event happened before or after another. The principle behind the asynchronous arbiter is that synchronization failure may be avoided by making the sampling system completely asynchronous. In essence, if no clock demands that the sampling system make its decision after a certain, fixed amount of time, system operation can be suspended until the decision has been resolved. Atypical CMOS arbiter is shown in FIG. 1. This is the commonly implemented R-S latch with a filtering circuit on the output. The arbiter works as follows: if it decides on a (i.e., it determines that a happened first), then output u is asserted. If the arbiter decides on b, then output v is asserted. The two inputs in this case are the unsynchronized input data and the synchronized clock (or control) signal.
In contrast to how this device is used in synchronous circuits, the asynchronous arbiter is allowed to go into a metastable state if the two inputs arrive nearly simultaneously. The filtering circuit on the output (a pass-gate-transformed pair of NOR gate/inverter hybrids) ensures that the arbiter outputs u and v do not change until the internal node voltages are separated by at least a p-transistor threshold voltagexe2x80x94meaning that the internal nodes have left the metastable state. At that time, the arbiter has xe2x80x9cmade up its mindxe2x80x9d and there is no possibility of an output glitch. Although the metastable state in theory can last forever, in practice it is usually a very short period. This is the reason that asynchronous arbiters are attractivexe2x80x94the average delay of the arbiter is likely to be much smaller than the latency that would be required to reduce the probability of synchronization failure to acceptable levels (in a synchronous implementation).
Expressed as a Production Rule Set (PRS), a rule set that acts as the blueprint for circuit building, the simple CMOS arbiter may be written as follows:                                                                         a                ⋀                t                            ↦                              s                ↓                                                                                                        b                ⋀                s                            ↦                              t                ↓                                                                                        ⫬                              a                ⋀                                  ⫬                                      t                    ↦                                          s                      ↑                                                                                                                                              ⫬                              b                ⋀                                  ⫬                                      s                    ↦                                          t                      ↑                                                                                                                              (        1        )            
A rule Gs↓ means that the variable s is set to false when the condition G is true. Rules of the form Gs↓ correspond to pull-down chains (meaning that the voltage of the signal s is being pulled down to a level representing false) and Gs ↑ correspond to pull-up chains (meaning that the voltage of the signal s is being pulled up to a level representing true). The xe2x80x9cxe2x80x9d symbol represents an xe2x80x9candxe2x80x9d. For example, in the first rule both a and t have to be true for s to be pulled down. The xe2x80x9cxe2x80x9d symbol represents taking a negation, which is done by taking the opposite value of the variable next to xe2x80x9cxe2x80x9d. So the third rule reads: xe2x80x9cIf the negation of a and the negation of t are both true then s is pulled up.xe2x80x9d From these production rules the circuit as shown in FIG. 1 is built. This circuit exhibits metastability when both input values a and b are true simultaneously.
A filtering circuit is introduced to prevent the outputs from changing until the arbiter has left the metastable state.
The arbiter is specified by the following handshaking expansion                     *                  [                      [                                                                                a                    →                                          u                      ↑                                                        ;                                ⁡                                  [                                      ⫬                    a                                    ]                                            ;                                                                    u                    ↓                                    ❘                                      b                    →                                          v                      ↑                                                                      ;                                  [                                      ⫬                    b                                    ]                                            ;                              v                ↓                                      ]                    ]                                    (        2        )            
The series of symbols can be understood as basic guidelines to determine the behavior of the arbiter. The first set of selection bracket xe2x80x9c[ . . . ]xe2x80x9d encloses another set of selection brackets. Inside, the xe2x80x9c|xe2x80x9d indicates that the arbiter is to choose one of the two clauses (separated by the xe2x80x9c|xe2x80x9d to execute. In each clause is a series of commands separated by semicolons. In the first line, the first command checks to see if a is true. If it is, then the output u is set to true. Then comes the selection of the negation of a and the resetting of u to false. The second line performs similar commands based on the value of b. At this stage the arbiter is reset and is ready to receive more input. The xe2x80x9c*xe2x80x9d symbol outside signifies that this process is performed repeatedly. The overall result is that if arbiter decides on a, then output u is asserted. If the arbiter decides on b, then output v is asserted.
One drawback of the arbiter circuit is that its operation depends on the fact that the inputs are stable, i.e., that the inputs remains asserted until the arbiter has acknowledged the input by making its decision. If one of the requests (inputs) is withdrawn before the arbiter has finally made its decision, the arbiter may fail (one or both of the outputs may glitch). FIG. 2 shows an example of what happens if an unstable input is sampled with a normal arbiter. In this figure, G0 represents the input to the arbiter, a 100 ps pulse, x.r1xe2x80x94 represents the switching internal node (between the R-S latch and the filter state), and x.x1 represents the output, which glitches. The drawback of the arbiter introduces the design goal of properly handling arbitrary, unstable signals, especially during the metastable state.
Q Modules
Another device that can be used for the purpose of synchronization in an asynchronous environment is called an implementation made up of Q Modules. It has been presented by Rosenberger et al. in the paper xe2x80x9cQ-modules: Internally Clocked Delay-Insensitive Modulesxe2x80x9d (IEEE Transactions on Computers, C37, 9, pp1005-1018, September 1988.) The overall architecture is a delay insensitive interconnection of medium sized sub circuits called Q modules. Each Q module is a standard synchronous like Finite State Machine with edge triggered flip flops, called Q flops, on its input, output and state signals. These special flip-flops use comparator-based circuits to acknowledge when metastability has resolved and values are stable. The acknowledgements from the Q-flops and the state registers are used to generate the next clock event.
QDI Model
Another goal within synchronizer design is to build the circuit so that it can be part of a Quasi Delay-Insensitive (QDI) asynchronous system. By definition, a QDI system is one whose correct operation does not depend on the physical delay of operators (active elements) or wires, which the exception of certain wires called xe2x80x9cisochronic forksxe2x80x9d that are arranged so as to be fast compared to the circuitry with which they communicate. The assumption that these wires are at least as fast as the circuitry is called the isochronic fork assumption. In practice violations of the isochronic fork assumption can occur in two ways. The first is that an isochronic fork may extend over a large distance, and the signals at the xe2x80x9ctinesxe2x80x9d of the fork are consequently delayed by different amounts. Making the isochronic fork assumption on long wires is generally avoided, although sometimes the extra cost of verifying the assumption is outweighed by a more convenient circuit implementation. The second way that the isochronic fork assumption can be violated is more sinister. In any digital system, the logic threshold of every operator will not be the same as that of every other operatorxe2x80x94this is particularly the case if early-threshold gates, due to dynamic circuit implementations, are mixed with combinational logic, as if often true in asynchronous systems. Therefore it must be ensured that the logic transitions on isochronic forks are fast compared to the delay of the gates attached to the outputs of the fork. The subtlety of QDI related issues also presents a challenge in synchronizer design.
Synchronizer Design
There have been attempts at designing a synchronizer that can be used in a asynchronous QDI system. In one attempt, to make the synchronizer QDI compliant, it was designed to produce a dual-rail output with the two rails representing the value of the sample input: either true of false. Each of the output rails encodes a bit and the two bits encode the observed input result as follows: xe2x80x9c00xe2x80x9dxe2x80x94no data, xe2x80x9c01xe2x80x9dxe2x80x940 (input was false), xe2x80x9c10xe2x80x9dxe2x80x941 (input was true), and xe2x80x9c11xe2x80x9dxe2x80x94error. As stated before, a synchronizer has two inputs: a control input and an input signal that is to be sampled. Informally, the specification of this synchronizer is that it waits for the control signal to be asserted and then samples the input. Using handshaking expansions, the program for this synchronizer is given by.                     *                  [                      [                                                                                re                    ⋀                                          ⫬                                              x                        →                                                  r0                          ↑                                                                                                      ;                                ⁡                                  [                                      ⫬                    re                                    ]                                            ;                                                r0                  ↓                                ❘                                                      re                    ⋀                    x                                    →                                      r1                    ↑                                                              ;                              [                                  ⫬                  re                                ]                            ;                              r                ⁢                                  xe2x80x83                                ⁢                                  1                  ↓                                                      ]                    ]                                    (        3        )            
where x is the input being sampled, re is the clocked control input, and the pair (r0, r1) is the dual-rail output. When the system environment (clock) asserts re, the synchronizer springs into action and samples x, returning the observed value by asserting either r0 (x was false) or r1 (x was true).
What makes the implementation of this circuit challenging is that x may change from true to false and vice versa at anytime. Sometimes this happens when an input request signal is first asserted and then withdrawn. If the input has a stable true value within a finite, bounded interval around the time control input arrives, the circuit asserts r1; if the input is a stable false, the circuit asserts r0. Otherwise if the input value is not stable in this time period, the circuit asserts either r0 or r1, but not both. In practice, this finite bounded time interval (or xe2x80x9cconfusion intervalxe2x80x9d) will be a very short time indeed, approximately the delay of the single inverter used to invert the input. The confusion interval is analogous to the setup and hold times of a latch. However, as opposed to a latch, the synchronizer is required to operate correctly (albeit non-deterministically) even if the input changes in this interval. In fact, the specification allows the input to be an arbitrarily narrow pulse, among other disconcerting signals. All that is really required of the input is that it be within the range of safe device operation to prevent the circuit from being damaged. Thus, the synchronizer design cannot safely assume a stable input even within the very short xe2x80x9cconfusion interval.xe2x80x9d
The fact that prior art synchronizer designs cannot handle a request that can be withdrawn at anytime has real life implications. This is because sometimes the ability to handle a withdrawn request is part of a system specification. The MIPS computer system ISA bus, for example, allows an external interrupt request to be withdrawn at anytime.
A Synchronizer Implementation
Based on the aforementioned synchronizer design, a synchronizer was implemented to solve the synchronization failure problem. The Production Rule Set (PRS) for the synchronizer is as follows:                                                         x              ↦                              x_                ↓                                                                                        ⫬                              x                ↦                                  x_                  ↑                                                                                                                        x                ⋀                re                ⋀                t                            ↦                              s                ↓                                                                                                        x_                ⋀                re                ⋀                s                            ↦                              t                ↓                                                                                        ⫬                              re                ⋀                                  ⫬                                      t                    ↦                                          s                      ↑                                                                                                                                              ⫬                              re                ⋀                                  ⫬                                      s                    ↦                                          t                      ↑                                                                                                                              (        4        )            
Unfortunately, this implementation was shown to be incorrect. Although the PRS shows that the implementation produces no illegal result, it is incorrect because it lacks a metastable state. In scenarios in which x changes close to the time when the sampling request on re arrives, the synchronizer must enter a metastable state (like the arbiter presented earlier). Otherwise it would be a bounded-delay synchronizer, contradicting the fact that it is impossible for a synchronizer to determine the order of two events within a bounded time period. The reason it does not have a metastable state can be understood by looking at the production rules. In the situation when x=false and re=true, the PRS (4) can be simplified to:                                                         s              ↦                              t                ↓                                                                                        ⫬                              t                ↦                                  s                  ↑                                                                                                        ⫬                              s                ↦                                  t                  ↑                                                                                        (        5        )            
The only stable state for this PRS is s=true, t=false, which is the desired outcome when x is false. However, if the device has only one stable state, then by calculus it cannot have a metastable state. To see how this is true, the metastable state can be considered as the peak of a hill. On both sides of the peak are valleys, symbolizing the stable states. The operation of a circuit in a metastable state is like a ball on the peak of the hill. The ball will eventually roll off of the peak into one of the valleys where it remains. This is analogous to the synchronizer having decided between one of two possible options. Since there are two valleys representing the two possible outcomes, it is impossible to have a metastable state with only one stable state. Without the metastable state, this circuit cannot possibly be a correct synchronizer.
It seems contradictory that even the production rules prevent the synchronizer from producing an illegal result, it is still shown to be incorrect. The only way to reconcile these facts is that the device enters a deadlocked state under some circumstances. To see how this may happen, consider the case that x is true when re is assertedxe2x80x94s will begin to fall (rule 3 of PRS). If x changes to false before s has fallen all the way, then t will begin to fall (rule 4 of PRS). If s has fallen far enough before this happens, then the device may get stuck in a state in which both s and t are in the intermediate range between a legal logic zero and legal logic one. Once this happens there is no rule in the PRS that will lead the circuit to another state. Thus it ends up in a deadlocked state.
Overall the challenge in synchronizer design is to solve the synchronization failure problem. Further it includes designing a QDI-compliant synchronizer that can handle arbitrary, unstable input signals correctly, especially during the metastable state. Finally, from observing prior art attempts, a correct design must have a metastable state.
The present invention provides a failure-free synchronizer. Unlike prior art synchronizers and asynchronous arbiters that produce glitches in their outputs, the present invention can sample an arbitrary and unstable inputs while maintaining zero probability of system failure.
In particular, embodiments of the invention address the synchronization failure problem and the lack of a metastable state in prior art synchronizers. The defects in prior art attempts have shown that the conditions rex and rex (where re is the control input and x is the data input) cannot be arbitrated. To overcome this problem, embodiments of the present invention introduce explicit signals a0 and a1 to hold the values rex and rex, respectively.
One embodiment of the present invention is a fast synchronizer. It has four main componentsxe2x80x94an input integrator, an inverting component, a SEL component and an output filter. The SEL component does the arbitration and is designed to operate with a metastable state. Since the fast synchronizer in some circumstances may not conform to the isochronic fork assumption, another embodiment is a safe synchronizer that fully meets the strictest QDI design requirements. The fork assumption is preserved as follows. Once the SEL component decides, the other input value (losing value) is also brought high to prevent a possible glitch due to an intermediate voltage value being interpreted as false by some components and true by others.
One embodiment of the present invention is a safe synchronizer that has uses a standard arbiter. In this embodiment, the values of a0 and a1 are reset in an order that allows the usage of a standard arbiter, which is desirable in keeping the number of xe2x80x9cblack boxesxe2x80x9d verification to a minimum. Another embodiment is a synchronizer with a xe2x80x9ckilablexe2x80x9d arbiter. The synchronizer in this embodiment disables the arbiter at appropriate times to simplify design and ensure correct operation.